//原文链接：https://blog.csdn.net/ITSOK_123/article/details/124141126

//哈希集合解法
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {		
    	//保存返回结果的set
        unordered_set<int> result_set;
        //保存中间结果的set
        unordered_set<int> uSet(nums1.begin(),nums1.end());
        for(auto s2:nums2){
            if(uSet.find(s2)!=uSet.end()){
                result_set.insert(s2);
            }
        }
        //使用set初始化结果vector
        vector<int>result(result_set.begin(),result_set.end());
        return result;
    }
};


//排序+双指针-1
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //分别对两个数组进行排序
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        //初始化结果向量数组
        vector<int> result;
        //初始化工作指针
        int i=0,j=0;
        int len1 = nums1.size(),len2 = nums2.size();
        //指针工作比较二者指向值是否相等
        while(i<len1 && j<len2){
        	int num1 = nums1[i],num2= nums2[j];
            if(num1<num2){
                i++;
            }else if(num1>num2){
                j++;
            }else{
                //这里要注意数组越界的情况
                result.push_back(num1);
                i++;
                j++;
                //注意这里对数组nums1和nums2进行去重，可以与后面的方法比较
                while(i<len1 && nums1[i]==nums1[i-1]){
                    i++;
                }
                while(j<len2 && nums2[j]==nums2[j-1]){
                    j++;
                }    
            }
        }
        return result;
    }
};

//排序+双指针-2
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int length1 = nums1.size(), length2 = nums2.size();
        int index1 = 0, index2 = 0;
        vector<int> intersection;
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
                // 保证加入元素的唯一性
                //注意这里直接在vector结果数组端进行去重
                if (!intersection.size() || num1 != intersection.back()) {
                    intersection.push_back(num1);
                }
                index1++;
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                index2++;
            }
        }
        return intersection;
    }
};
